package com.simple;

import java.util.*;

/**
 * 1122. 数组的相对排序
 * 给你两个数组，arr1 和 arr2，
 * arr2 中的元素各不相同
 * arr2 中的每个元素都出现在 arr1 中
 * 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
 * 示例：
 * <p>
 * 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
 * 输出：[2,2,2,1,4,3,3,9,6,7,19]
 *  
 * <p>
 * 提示：
 * <p>
 * arr1.length, arr2.length <= 1000
 * 0 <= arr1[i], arr2[i] <= 1000
 * arr2 中的元素 arr2[i] 各不相同
 * arr2 中的每个元素 arr2[i] 都出现在 arr1 中
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/relative-sort-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Question1122 {

    public static void main(String[] args) {
        int[] arr1 = new int[]{2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19, 10};
        int[] arr2 = new int[]{2, 1, 4, 3, 9, 6};
        System.out.println("[data] = " + Arrays.toString(relativeSortArray(arr1, arr2)));
    }

    /**
     * 思路
     * 1. 双指针 遍历arr2
     * 2. [指针1] 默认指向第一个元素，依次根据arr2元素往后遍历
     * 3. arr2 元素 与指针所在位置相等，替换当前元素与指针位，指针位+1
     * 4. 第一次循环结束，再遍历后续指针，进行冒泡排序
     */
    private static int[] relativeSortArray(int[] arr1, int[] arr2) {
        // 遍历arr2 交换排序arr1中含有arr2的元素
        int index = 0;
        for (int num : arr2) {
            for (int i = 0; i < arr1.length; i++)  {
                if (arr1[i] == num) {
                    // 指针位 元素互换
                    int temp = arr1[index];
                    arr1[index] = num;
                    arr1[i] = temp;
                    index++;
                }
            }
        }

        // 剩余元素，冒泡排序
        for (int i = index; i < arr1.length; i++) {
            for (int j = i + 1; j < arr1.length; j++) {
                if (arr1[i] > arr1[j]) {
                    // 指针位 元素互换
                    int temp = arr1[i];
                    arr1[i] = arr1[j];
                    arr1[j] = temp;
                }
            }
        }

        return arr1;
    }
}
